//归并排序就像是组织一场元素之间的“比武大会”，这场比武大会分成两个阶段。
// 1. 分组
//2. 归并
//既然分了组，接下来就要开始“比武”了。
//归并排序和擂台赛有一个很大的不同，就是擂台赛只需要决定谁是老大，而并不关心谁做老二和老三；归并排序的要求复杂一些，需要确定每一个元素的排列位置。
//因此，当每个小组内部比较出先后顺序以后，小组之间会展开进一步的比较和排序，合并成一个大组；大组之间继续比较和排序，再合并成更大的组……最终，所有元素合并“成了一个有序的集合。



function mergeSort(array, start,  end) {
    if (start < end) {
        //折半成两个小集合，分别进行递归
        let mid = Math.floor((start + end) / 2);
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);
        //把两个有序小集合，归并成一个大集合
        merge(array, start, mid, end);
    }
    return array;
}

function merge( array,start, mid, end) {
    //开辟额外大集合，设置指针
    let tempArray = [];
    let p1 = start;
    let p2 = mid + 1;
    let p = 0;
    //比较两个小集合的元素，依次放入大集合
    while ((p1 <= mid) && (p2 <= end)) {
        if (array[p1] <= array[p2]) {
            tempArray[p++] = array[p1++];
        }
        else {
            tempArray[p++] = array[p2++];
        }
    }
    //左侧小集合还有剩余，依次放入大集合尾部
    while (p1 <= mid) {
        tempArray[p++] = array[p1++];
    }
    //右侧小集合还有剩余，依次放入大集合尾部
    while (p2 <= end) {
        tempArray[p++] = array[p2++];
    }
    //把大集合的元素复制回原数组
    for (let i = 0; i < tempArray.length; i++) {
        array[i + start] = tempArray[i];
    }
}

let array = [ 5, 8, 6, 3, 9, 2, 1, 7 ];
console.log(mergeSort(array, 0, array.length - 1));